%\usepackage{graphicx}
\chapter {Introduction}
\pagenumbering{arabic}
Computer research nowadays aims at facilitating computer human interaction in every way. Pen-based interfaces give the user a pencil-paper like feeling that enhances interaction more than the current used keyboard-mouse computer interfaces. However, until now there are hardly any complete pen based computer systems. Generally, Current Pen-Based systems make use of the Pen or stylus to perform the same role as the mouse / keyboard. A minority of such systems are equipped with handwriting or digit recognition that is typically restricted for specific language. 

\section{Sketch Recognition}
Sketch recognition is defined as the process of identifying symbols that users draw using single or multiple strokes. Users draw strokes using a pen and the system should immediately interprets their strokes into objects that can be easily manipulated.

Sketches here stand for any hand drawing the user draws using digital stylus or similar device. Normally, sketches are composed of a set of strokes. The time between pen-up and pen-down events identify each stroke. The strokes are mainly the path of points, which the user path through between the pen-down and pen-up events while using the stylus or similar device. 
  
\section{Importance of Sketch Recognition}
\label{sec:ImportanceOfSketchRecognition}
Scientists generally, and engineers specifically express thoughts and designs using sketches. Engineers use sketches to exchange designs as a natural method of communication rather than writing or speaking. Engineers use paper and pencil design in early stages of design. The sketching process itself goes through numerous stages. Firstly, early stages with rough drafting designs or notations are mainly done using paper and pencil. These primary rough sketches are edited and altered until they are stabilized and finally they are transformed into the computer. 

 Paper and Pencil are preferred in design as they offer a remarkable ease in editing and altering the primary rough sketches. Current CAD systems do not give the designer the ease of altering the early designs. Designer had to sketch primary designs on paper and pencil, next the final design is transferred into computer using a CAD system menus. The process is time consuming and tiring. The need for fast design and development process is driven by the fast growing industries and technology.
 
 A sketch recognition and understanding system will provide a powerful tool to the designers to draw sketch as they usually draw using paper and pencil with the advantages of a computer program. Designers need a normal sketching environment that will provide him facilities in paper interface and the modifying and simulation that is in current CAD systems. 
 
\section{Applicability }
% talk about application like cad systems, software engineering uml diagrams ....
% meeting idea brainstorming , mind mapping string ..
% communication program  
% sketching programs ...
Applications of sketch recognition rang from engineering device simulation to design. Drawing and sketching programs are most likely to benefit from integrating a sketch recognition system into their design environments. Other applications include object retrieval, map navigations and various engineering design systems.

\section{Problem Definition and Challenges}
\label{sec:ProblemsAndChallenges}

Understanding hand drawn sketches may be trivial for humans but it is a challenging problem when speaking about computer-based system. Most of the research made on the sketch recognition is achieved for one particular domain or for strictly a set of pre-defined symbols\cite{Vibratory8,physicalmeaning6}. Furthermore, others restrict the user the freedom in drawing which loose the main goals of paper-like-interface systems\cite{gestureexample12,aideddesgin22,sketchinginterfaces2}. The only few systems that have achieved the desired degree of freedom for the users are extremely computationally expensive\cite{EfficientAbstract39,SketchRead2007}.

Similar to most recognition system, sketch recognition is divided into three steps: preprocessing, segmentation and symbol recognition. The preprocessing phase captures user input stroke points and collects basic information about the stroke then proceeds to remove noise and compute basic statistical and geometrical information. In the segmentation phase, the strokes are divided into a set of simple geometrical primitives or segments. In the third phase, sketch recognition, strokes and segments are clustered to formulate symbols that can be recognized by a classifier system.
There are several problems in this research area that need to be handled to implement an integrated sketch recognition system. The fact that the user draws strokes in a spontaneous and ambiguous manner intensifies the challenges. One of the main problems is segmenting spontaneous strokes drawn by the user into geometrical primitive segments. Another major problem is the high level of ambiguities in the drawing. The next sections describe each problem in details. 


\subsection {Segmentation}
The goal of segmentation is dividing the strokes into the geometric primitive's as lines, arcs, and ellipses. The strokes, as mentioned before are the path of points between pen-down and pen-up events while using a stylus. Furthermore, after identifying a stroke, it should be processed to detect the critical points or vertices which divide the stroke into segments. Later, each segment is classified as line, arc, ellipse or circle. The main problem in this process is detecting the critical points and vertices which divide strokes into lines and arcs. The user draws the lines and arcs in an undefined manner which make it difficult for the program to decide where the user had finished a line and started a new arc or vice verse;  Figure \ref {fig:strokeinterpolation}.
\begin{figure}

\begin{center}
		\includegraphics[scale=0.6]{../../neededfiles/Figures/strokeinterpolation.eps}
	\caption[Segmentation Error]{Different ways for segmenting a stroke drawn by user. a) The stroke users draw b)interpretation as two line segments c) interpretation as an arc. This example is adapted from \cite{earlyprocess}}
	%The figure shows an arc that the user draw which can be segmented in different ways as a single line or as an arc where a) The stroke users draw  b)interpretation as a single line segment b) interpretation as an arc.}
	\label{fig:strokeinterpolation}
\end{center}
\end{figure}

\subsection{Ambiguity}
Figure \ref{fig:VorU} shows an example of ambiguity, where the strokes drawn by the user can be classified in several ways. The nature of hand drawn sketch itself is highly ambiguous even for human eye. You may see two drawings you cannot decide if they are a square or a rectangle.

The ambiguities in sketch understanding are found at many levels in the system. Firstly, in the segmentation phase, a single stroke can be interpreted as an ellipse or as a circle. Symbol ambiguity is another problem as a symbol can have more than one interpolation. Due to the user's sloppy drawing the symbols can have more than one interpolation which varies with the domain drawn in it. A similar problem was faced in handwriting recognition (Figure \ref{fig:VorU}). The problem could be solved by providing context or domain information which could not be provided in most sketches. 

\begin{figure}	
	\centering
		\includegraphics[scale=0.65]{afterDefense/Amb.jpg.eps}
	\caption[Handwriting Ambiguities] {The same handwriting can be interpreted differently in various contexts; In the first line the b can be viewed as a B and in the second one could see it as 8. This example is adapted from \cite{ambiguityWebsite}.  }
\label{fig:VorU}
\end{figure} 	

\section{Research Scope}
%rewirte this part.............................
%  research will investigated till sketch recognition in domain of uml diagrams. 
%this research will include investigating the best method to recognize sketches.  The scope of the research will include recognizing various sketches. The methods used in this research are comparing current systems and enhancing them and adopting them into simple geometrical symbols.  Using well established AI methods specially \textit{Swarm Intelligence} to solve the problem. 
This research presents a new method for sketch recognition. The scope of the research includes recognizing various symbols drawn using single and multiple strokes. The research compares various segmentation methods. This research used two Particle Swarm Optimization (PSO) \cite{PSOFirst} methods to segment strokes into geometrical primitives. The research also investigates various spatial, geometrical and statistical feature sets used in sketch recognition. A Support Vector Machines (SVM) classifier \cite{svmintroduce} is used to classify the sketch into one of symbols from the set of previously trained symbols. This research targets the recognition of one symbol at a time. The symbol may be drawn in one or more stroke without any restriction on order, orientation or style.

%This research assumes the user draws one symbols at a time. The user can draw can draw this symbol in one stroke or in multiple stroke without any restriction on order, orientation or style.  
 
\section{Thesis Overview}
This thesis is arranged as follows: chapter \ref{sec:survey} presents a survey of different components of the sketch recognition. Chapter \ref{sec:ParticleSwramOptimization} gives a review on swarm intelligence and particle swarm optimization.  Chapter \ref{sec:proposedSystem} describes the proposed system and its main building blocks. The comparative study of the different techniques and their detailed results in various experiments are given in chapter \ref{sec:Evaluation}. Finally, chapter \ref{sec:DiscussionConclusion} presents the conclusions of this thesis and suggested future work.

